package com.fanshuai.algorithms.divide;

/**
 * 给定n个元素的整数列（可以能为负整数）,a1,a2,…,an。求数列的字段，使其和最大。
 例如：当(a1, a2, a3, a4, a5, a6)=(-2, 11, -4, 13, -5, -2)时，最大子段和为sum(11-4+13)=20。
 */
public class MaxSubArrSum {
    /**
     * 动态规划解法
     * dp[i][j]表示 [i..j]子数组的字段和
     * dp[i][j] = dp[i+1][j] + a[i]  0<=i<n, i<=j<n
     * @param a
     * @return
     */
    public static int maxSubArr(int[] a) {
        int max = Integer.MIN_VALUE;

        int n = a.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = a[i];
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = a[i] + dp[i + 1][j];

                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }

        return max;
    }

    /**
     * 分治法实现  子问题有重叠，需要分情况合并子问题
     *
     * 将数组a拆分为2个子数组，子数组的最大和为maxLeft, maxRight. 分三种情况：
     * 数组最大和在左子数组，返回maxLeft
     * 数组最大和在右子数组，返回maxRight
     * 数组最大和在两个数组都有，分别取左右子数组最大和，相加
     * @return
     */
    public static int maxSubArrDivide(int[] a) {
        return maxSubArrDivide(a, 0, a.length - 1);
    }

    private static int maxSubArrDivide(int[] a, int left, int right) {
        if (left == right) {
            return a[left];
        }

        int mid = (left + right) / 2;
        int maxLeft = maxSubArrDivide(a, left, mid);
        int maxRight = maxSubArrDivide(a, mid + 1, right);

        //第三种情况，此时a[mid]和a[mid+1]都在子数组中
        int sum1 = 0, max1 = 0, sum2 = 0, max2 = 0;
        for (int i = mid; i >= left; i--) {
            sum1 += a[i];
            if (sum1 > max1) {
                max1 = sum1;
            }
        }
        for (int i = mid + 1; i <= right; i++) {
            sum2 += a[i];
            if (sum2 > max2) {
                max2 = sum2;
            }
        }
        int maxAll = max1 + max2;

        int maxSub = Math.max(maxLeft, maxRight);
        return Math.max(maxAll, maxSub);
    }

    public static void main(String[] args) {
        int[] a = {-2, 11, -4, 13, -5, -2};

        System.out.println(maxSubArr(a));
        System.out.println(maxSubArrDivide(a));
    }
}
